In the field of what could be broadly referred to as map or path processing, the least-cost path problem is important in a variety of military, space, and research applications. In this regard, the term "cost" can refer to a variety of things from actual dollars and cents to the loss of human life. The problem can be characterized as follows--given a map of some "space" where the space comprises a plurality of nodes interconnected by paths which can be selectively taken and wherein each of the nodes (i.e. points or areas) has associated therewith a cost of traversing that node; find the least cost path of traveling from one particular originating node to another node and find the cost of that traversing. For example, on a battlefield it is desired that tanks be driven from one position to another. From surveillance and satellite information, the difficulty of driving a tank across each ten foot square quadrant (i.e. node) is know (taking into account the slope of the land, vegetation, lakes, etc.). From this information, as well as knowledge of enemy positions and weapons capability, a cost function can be calculated and assigned to each quadrant. The problem is to find the best route for the tank movement--in the shortest possible time.
Solving such problems according to prior art computing techniques becomes very time intensive on serial computer as the number of nodes (or quadrants in the above-described example) increases. Heuristic means are usually employed to find a solution, with the consequent loss of guarantee that the best path will be found. Furthermore, a significant advantage in tactical problems (such as the tank problem), and the like, if the solution can be found in real time. To illustrate this point, suppose the tanks as postulated above have succeeded in reaching the half-way point of their journey when new information becomes available (such as the discovery of an uncharted bog in their path or a sudden and unexpected shift in enemy firepower). If the new information could be promptly incorporated into the path-finding system, a new "best path" could be determined thus possibly saving the tanks from enemy annihilation. Certainly the tank commanders will not wish to wait while some behind the lines mainframe computer grinds away on the problem. They need answers and they need them fast.
In the prior art, this type of problem is usually formulated in a different way for computing purposes; that is, the nodes are commonly considered to be cost-free and costs are incurred at the edges, i.e. in the paths between nodes. Such an arrangement is shown in simplified form in FIG. 1. The nodes 10 (labelled A-G for convenience) are, in fact, switching points while the connecting paths 12 are given a weighted value corresponding to the cost of traversing. In a digital computer implementation, this is typically accomplished with software while in an analog computational system the paths 12 would be assigned some sort of measurable electrical characteristic and the nodes 10 would actually accomplish switching functions as the various paths were tried and measured. Thus, in either approach, to find the costs of the various ways of getting from node "A" to node "G", one would (either electrically or through software depending on the implementation) use some sort of path analysis capability 14 to try the various paths by trial and error to determine the cost of each and thereby the lowest-cost path by comparison. Obviously, such a serial approach is far from "real-time" and is not prone to instant reconfiguration in the event of updates to information. Such an approach is described in greater detail in "Mathematical Programming and Electrical Networks" by J. B. Dennis, MIT Press 1959, a copy of which is filed herewith.